/*!
 * \file heurPartiteSubgraph.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heurSelColoring.h>

static BitMap * RR; 		//!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; 		//!< Input graph of the heuristics.
static size_t memsz = 0;	//!< Memory space used by the heuristics.

// mcsColoring
static int * nextInColor = NULL; //!< Vertices classified by colors

void initHeur(Graph * g) {
	heurg = g;

	RR = (BitMap *) newBitMap(g->n);

//	memsz += (nnodes << LOGW);
	nextInColor = NULL;
}

void closeHeur() {
	freeBitMap(RR);
//	free(RR);

	RR = NULL;
	heurg = NULL;

	if (nextInColor != NULL) {
		free(nextInColor);
		nextInColor = NULL;
	}
}

size_t getMemSize() {
	return memsz;
}

/*!
 * \fn int maxClique(BitMap * R)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 *
 * \return The size of the clique found.
 */
int maxClique(BitMap * R) {
	int size = 0;
	Node nodeRR;

	printf("maxclique:");

	copyAll(RR, R);
	for (begin(RR, &nodeRR); !end(&nodeRR); next(&nodeRR)) {
		printf(" %d",getElement(&nodeRR));
		retainFrom(RR, neig(heurg, getElement(&nodeRR)), &nodeRR);
//		delElement(RR, &nodeidx);

		size++;
	}

	printf("\n");

	return size;
}

/*!
 * \fn int greedyColoring(BitMap * R, int lim)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * \param R Input bitmap of vertices to color.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
int greedyColoring(BitMap * R, int lim) {
	int size = 0;
	Node nodeR;
	Node nodeRR;

	begin(R, &nodeR);
	beginWhile(RR, &nodeRR);
	while (size < lim && !end(&nodeR)) {
		copySets(&nodeRR, &nodeR);
		do {
			removeFrom(&nodeRR, neig(heurg, getElement(&nodeRR)));
//			delElement(RR, &nodeRR);
			delElement(R, &nodeRR);
			next(&nodeRR);
		} while (!end(&nodeRR));

		size++;
		next(&nodeR);
	}

	return size;
}

/*!
 * \fn void mcsRecolor(BitMap * R, int size)
 * \brief Greedy heuristic for recoloring vertices by color exchanges.
 *
 * For every vertex \c p in the input bitmap, attempt to find a vertex \c q in the \c cover array such that the number of neighbors \c r
 * of \c p in the color \c k1 of \c q is at most 1. If such \c q is found, there are two cases. If \c r \c = \c 0, then add \c p to color
 * \c k1, updating \c cover and \c idx arrays. If \c r \c = \c 1, then attempt to find a color \c k2 containing no neighbors
 * in color \c k2. If such color \c k2 is found, then move \c q to color \c k2 and add \c p to color \c k1, removing it from the
 * input bitmap.
 *
 * \param R Input bitmap of vertices to color.
 * \param size Number of colors.
 *
 * \return The number of colors used.
 */
static void mcsRecolor(BitMap * R, int size) {
	int sentinel = heurg->n << 1;

	Node node;
	int u = 0, v = 0, prevu, hasv;
	copyAll(RR, R);
	for (begin(RR, &node); (hasv = !end(&node)); next(&node)) {
		v = getElement(&node);
		int ucolor = 0;
		while (ucolor < size - 1) {
			int curInColor = nextInColor[heurg->n + ucolor];
			int prevInColor = heurg->n + ucolor;
			int hasNeig = 0;
			while (hasNeig < 2 && curInColor < heurg->n) {
				if (hasEdge(heurg, v, curInColor)) {
					hasNeig++;
					u = curInColor;
					prevu = prevInColor;
				}
				prevInColor = curInColor;
				curInColor = nextInColor[curInColor];
			}

			if (hasNeig < 2) {
				int w, wcolor = -1;
				if (hasNeig == 0) {
					w = v;
					wcolor = ucolor;
				} else {
					int cl = ucolor + 1;
					while (cl < size) {
						int cc = nextInColor[heurg->n + cl];
						while (cc < sentinel && !hasEdge(heurg,u,cc))
							cc = nextInColor[cc];
						if (cc == sentinel) {
							w = u;
							wcolor = cl;
							nextInColor[prevu] = nextInColor[u];
							nextInColor[v] = nextInColor[heurg->n + ucolor];
							nextInColor[heurg->n + ucolor] = v;
							cl = size;
						} else
							cl++;
					}
				}

				if (wcolor >= 0) {
					nextInColor[w] = nextInColor[heurg->n + wcolor];
					nextInColor[heurg->n + wcolor] = w;
//					delElement(RR, &node);
					delElement(R, &node);
					ucolor = size;
					hasv = 0;
				}
			}
			ucolor++;
		}

		if (hasv)
			retainAll(RR, neig(heurg, v));
	}
}

/*!
 * \fn int stackColoring(BitMap * R, int lim)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 * The colors created are represented in \c cover and \c idx arrays.
 *
 * \param R Input bitmap of vertices to color.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
static int stackColoring(BitMap * R, int lim) {
	int sentinel = heurg->n << 1;

	if (nextInColor == NULL) {
		nextInColor = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	nextInColor[heurg->n] = sentinel;

	int size = 0;
	Node nodeR;
	Node nodeRR;

	begin(R, &nodeR);
	beginWhile(RR, &nodeRR);
	while (size < lim && !end(&nodeR)) {
		copySets(&nodeRR, &nodeR);
//		printf("greedy-cor %d:",size);
//		printSetNodes(RR);
		do {
			int v = getElement(&nodeRR);
//			printf(" %d",v);
			removeFrom(&nodeRR, neig(heurg, v));
//			delElement(RR, &nodeRR);
			delElement(R, &nodeRR);

			nextInColor[v] = nextInColor[heurg->n + size];
			nextInColor[heurg->n + size] = v;
			next(&nodeRR);
		} while (!end(&nodeRR));

		nextInColor[heurg->n + (++size)] = sentinel;
		next(&nodeR);

//		printf("\n");
	}

	return size;
}

/*!
 * \fn int mcsColoring(BitMap * R, int lim)
 * \brief Greedy heuristic for vertex coloring, with vertex recoloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
int mcsColoring(BitMap * R, int lim) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(R, lim);

	int size = stackColoring(R, lim);
//	printStackColor(size);
	if (lim == size && isNotEmpty(R))
		mcsRecolor(R, size);

	return size;
}

void mcsColoring_f(BitMap * R, int lim) {
	if (lim <= 1)
		greedyColoring(R, lim);
	else {
		int size = stackColoring(R, lim);
		if (isNotEmpty(R))
			mcsRecolor(R, size);
	}
}
